| BlockBuilder generates blocks where keys are
| prefix-compressed:
|
| When we store a key, we drop the prefix shared
| with the previous string. This helps reduce
| the space requirement significantly.
| Furthermore, once every K keys, we do not apply
| the prefix compression and store the entire
| key. We call this a “restart point”. The tail
| end of the block stores the offsets of all of
| the restart points, and can be used to do
| a binary search when looking for a particular
| key. Values are stored as-is (without
| compression) immediately following the
| corresponding key.
|
| An entry for a particular key-value pair has the form:
| shared_bytes: varint32
| unshared_bytes: varint32
| value_length: varint32
| key_delta: char[unshared_bytes]
| value: char[value_length]
| shared_bytes == 0 for restart points.
|
| The trailer of the block has the form:
| restarts: uint32[num_restarts]
| num_restarts: uint32
|
| restarts[i] contains the offset within the
| block of the ith restart point.
| BlockHandle is a pointer to the extent
| of a file that stores a data block or a
| meta block.
|
| Helper class for tests to unify the interface
| between BlockBuilder/TableBuilder
| and
|
| Block/Table.
|
| Footer encapsulates the fixed information
| stored at the tail end of every table
| file.
|
| Cleanup functions are stored in
| a single-linked list.
|
| The list’s head node is inlined in the
| iterator.
| A internal wrapper class with an interface
| similar to Iterator that caches the valid() and
| key() results for an underlying iterator.
|
| This can help avoid virtual function calls and
| also gives better cache locality.
| A Table is a sorted map from strings to
| strings. Tables are immutable and persistent.
| A Table may be safely accessed from multiple
| threads without external synchronization.
| TableBuilder provides the interface used to
| build a Table (an immutable and sorted map from
| keys to values).
|
| Multiple threads can invoke const methods on
| a TableBuilder without external
| synchronization, but if any of the threads may
| call a non-const method, all threads accessing
| the same TableBuilder must use external
| synchronization.
| An internal iterator. For a given
| version/level pair, yields information about
| the files in the level. For a given entry,
| key() is the largest key that occurs in the
| file, and value() is an 16-byte value
| containing the file number and file size, both
| encoded using EncodeFixed64.